// https://leetcode.cn/problems/lemonade-change/description/

// 算法思路总结：
// 1. 贪心策略处理柠檬水找零问题
// 2. 维护5元、10元、20元的数量统计
// 3. 收到5元直接收下，10元需要找5元，20元优先用10+5找零，其次用3张5元
// 4. 无法找零时立即返回false，全部处理成功返回true
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    bool lemonadeChange(vector<int>& bills) 
    {
        int m = bills.size();

        int five = 0, ten = 0, twenty = 0;
        for (const int& num : bills)
        {
            if (num == 5)
                five++;
            else if (num == 10)
            {
                if (five >= 1)
                {
                    five--;
                    ten++;
                }
                else return false;
            }
            else if (num == 20)
            {
                if (five >= 1 && ten >= 1)
                {
                    five--;
                    ten--;
                    twenty++;
                }
                else if (five >= 3)
                {
                    five -= 3;
                    twenty++;
                }
                else return false;
            }
        }

        return true;
    }
};

int main()
{
    vector<int> v1 = {5,5,5,10,20}, v2 = {5,5,10,10,20};
    Solution sol;

    cout << sol.lemonadeChange(v1) << endl;
    cout << sol.lemonadeChange(v2) << endl;

    return 0;
}
